#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/16 10:59
# ===========================================
#       题目名称： 10. 正则表达式匹配
#       题目地址： https://leetcode.cn/problems/regular-expression-matching/
#       题目描述： https://note.youdao.com/s/aSyZ5Ulm
# ===========================================


class Solution:
    """
        '.' 匹配任意单个字符
        '*' 匹配零个或多个前面的那一个元素
    """

    def isMatch(self, s, p):
        m, n = len(s), len(p)

        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # 初始化
        dp[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

        # 状态更新
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':  # 【题目保证'*'号不会是第一个字符，所以此处有j>=2】
                    if s[i - 1] != p[j - 2] and p[j - 2] != '.':
                        dp[i][j] = dp[i][j - 2]
                    else:
                        dp[i][j] = dp[i][j - 2] | dp[i - 1][j]

        return dp[m][n]


if __name__ == '__main__':
    s = Solution()
    # False
    print("False =>", s.isMatch(s="aa", p="a"))
    # True
    print("True =>", s.isMatch(s="aa", p="a*"))
    # True
    print("True =>", s.isMatch(s="ab", p=".*"))
